#include<bits/stdc++.h>
using namespace std;
const __int128 one = 1;
long long MOD1 = 0;
long long exgcd(long long a,long long b,long long &x,long long &y){
	if(!b){
		x = 1;
		y = 0;
		return a;
	}
	long long tx,ty;
	long long g = exgcd(b,a%b,tx,ty);
	x = ty;
	y = tx - (a/b)*ty;
	return g;
}
int main(){
	long long g,m;
	cin>>g>>MOD1;	
	MOD1*=MOD1;
	long long x,y;
	long long gc = exgcd(g,MOD1,x,y);
	if(gc != 1){
		cout<<"不存在\n";
		return 0;
	}
	x = (x%MOD1 + MOD1)%MOD1;
	cout<<x<<'\n';
}